package 数组算法;

import java.util.HashSet;
import java.util.Set;

public class longestConsecutive128 {
    /**
     * 最长连续序列
     * <p>
     * 1 将数组排序 然后判断前面是否为后面的+1 如果是count++ 如果不是那就比较max值和count谁大 时间复杂度为nlog(n)
     * <p>
     * 2 将数组进行去重处理  然后再遍历一次数据存储在hashmap中  然后再进行一次遍历 通过判断这个数的下一个是否在map中的 然后在
     *
     * @param nums
     * @return
     */
    public int longestConsecutive(int[] nums) {
        // 去重进行处理
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }
        // 最大的连续的长度是0
        int longestStreak = 0;

        // 遍历数组
        for (int num : num_set) {
            // 判断是否包含 当前的数组的小于1在set中 如果在那就设置
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                // 循环的判断时候存在数组大于1的
                while (num_set.contains(currentNum + 1)) {
                    // 那就直接复制 同时将最长的值家那个1
                    currentNum += 1;
                    currentStreak += 1;
                }
                // 每次走完一个数组都更新一下当前最大长度
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }
}
